package 力扣._45_跳跃游戏2;

class Solution {
    public int jump(int[] nums) {

        // 选择当前位置i能跳到的位置j中nums[j]最大的, 这样跳的范围更大

        int i = 0, sum = 0;
        while (i < nums.length - 1) {
            if (nums[i] + i >= nums.length - 1) {
                sum++;
                break;
            }
            int max_j_index = i + 1;
            for (int j = i + 2; j <= i + nums[i]; j++) {
                if (max_j_index + nums[max_j_index] <= j + nums[j])
                    max_j_index = j;
            }
            sum++;
            i = max_j_index;

        }
        return sum;
    }

    public static void main(String[] args) {
        int jump = new Solution().jump(new int[]{1,2, 1, 1, 1});
        System.out.println(jump);
    }
}